package sliding_window

import "sort"

/*
给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

思路：
1.特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
2.对数组进行排序。
3.遍历排序后数组：
	若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
	对于重复元素：跳过，避免出现重复解
	令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
		当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
		若和大于 0，说明 nums[R] 太大，R 左移
		若和小于 0，说明 nums[L]太小，L 右移

*/
func threeSum(nums []int) [][]int {
	//参数判断
	if len(nums) < 3 {
		return [][]int{}
	}

	//排序
	sort.Ints(nums)

	n, res := len(nums), make([][]int, 0)

	for i := 0; i < n; i++ {
		//因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果
		if nums[i] > 0 {
			return res
		}
		//避免出现重复
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		l, r := i+1, n-1
		for l < r {
			if nums[i]+nums[l]+nums[r] == 0 {
				res = append(res, []int{nums[i], nums[l], nums[r]})

				//寻找新的解，排除连续相等的数
				for l < r && nums[l] == nums[l+1] {
					l++
				}
				for l < r && nums[r] == nums[r-1] {
					r--
				}
			}

			//如果sum小于0，说明nums[l]太小了，L需要右移动
			if nums[i]+nums[l]+nums[r] < 0 {
				l++
			} else {
				// 如果sum大于0，说明nums[r]太大了，R左移
				r--
			}

		}
	}
	return res
}

// 官方题解：排序+双指针
func threeSum1(nums []int) [][]int {
	//排序
	sort.Ints(nums)

	n, ans := len(nums), make([][]int, 0)

	//枚举 A
	for first := 0; first < n; first++ {
		//判重，需要和上一次枚举的数不相同
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		// c 对应的指针初始指向数据的最右端
		//第三重循环变成一个从数组最右端开始向左移动的指针
		third := n - 1
		target := -1 * nums[first]
		//枚举 b
		for second := first + 1; second < n; second++ {
			//判重，需要和上一次枚举的数不相同
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}
			//需要保证b的指针在c的指针的左侧，如果和不等于0 ，则移动c指针左移
			for second < third && nums[second]+nums[third] > target {
				third--
			}
			//如果指针重合，随着b后续的增加就不会有满足a+b+c=0并且b <c 的c了，可以退出循环
			if second == third {
				break
			}

			if nums[second]+nums[third] == target {
				ans = append(ans, []int{nums[first], nums[second], nums[third]})
			}
		}
	}
	return ans
}

//最优解，双指针+排序
func threeSum2(nums []int) [][]int {
	//排序
	sort.Ints(nums)
	result, start, end, index, addNum, length := make([][]int, 0), 0, 0, 0, 0, len(nums)
	for index = 1; index < length-1; index++ {
		start, end = 0, length-1
		if index > 1 && nums[index] == nums[index-1] {
			start = index - 1
		}

		for start < index && end > index {
			if start > 0 && nums[start] == nums[start-1] {
				start++
				continue
			}
			if end < length-1 && nums[end] == nums[end+1] {
				end--
				continue
			}
			addNum = nums[start] + nums[end] + nums[index]
			if addNum == 0 {
				result = append(result, []int{nums[start], nums[index], nums[end]})
				start++
				end--
			} else if addNum > 0 {
				end--
			} else {
				start++
			}

		}

	}
	return result
}
